Genetic Algorithm

Author

Gabriel Rączowksi

Solving traveling salesman problem using genetic algorithm

Traveling salesman problem is classified NP-hard problem. Salesman wants to visit all cities, each city only once and wants to take the fastest route. Calculating distances for all permutations and choosing best one is first idea that comes to mind. This comes with factorial growth: 20 cities mean 2.43*10^18 permutations.



Genetic algorithm is random based tool. It is inspired by natural processes such as natural selection and evolution. It simulates population and in each new generation better, stronger individuals have higher chances of being selected to reproduce and pass characteristics to the next generation.

Workflow

  1. Generating population
  2. Calculating loss function
  3. Choosing randomly individuals who reproduce
  4. Crossovers and mutations
  5. Loop to 2.


Results and conclusions

Parameters:
-50 generations
-12 cities
-100 - population size


Loss function plot In each next generation results tend to be better - distance travelled is lower.

Visualisation of each generation.

At the beginning, route changes significantly between generations, but later the improvements become smaller.